package com.kevin.Code.DP;

/**
 * @author Vinlee Xiao
 * @Classname LastStoneWeightii
 * @Description Leetcode  1049. 最后一块石头的重量 II 中等难度 背包问题 有点难以理解
 * @Date 2021/10/9 21:28
 * @Version 1.0
 */
public class LastStoneWeightii {

    /**
     * 转化成背包问题有点难
     * 要使最后一块石头的值较小 两堆石头的值应该接近sum/2
     *
     * @param stones
     * @return
     */
    public int lastStoneWeightII(int[] stones) {

        int len = stones.length;

        if (len == 0) {
            return stones[0];
        }

        int sum = 0;
        for (int stone : stones) {
            sum = sum + stone;
        }

        //理想情况 分为两堆 相减为0
        int target = sum / 2;

        //表示前0...i个石头能够凑出target 的最大石头数
        int[] dp = new int[target + 1];

        //1.首先明确动态dp[]数组的含义


        for (int stone : stones) {

            for (int i = target; i >= stone; i--) {

                dp[i] = Math.max(dp[i], dp[i - stone] + stone);
            }
        }

        return sum - 2 * dp[target];
    }


    public int lastStoneWeightII1(int[] stones) {
        int len = stones.length;

        if (len == 1) {
            return stones[0];
        }

        int sum = 0;
        for (int stone : stones) {
            sum = sum + stone;
        }

        //理想情况 分为两堆 相减为0
        int target = sum / 2;

        //dp数组的含义表示前i个数能够在容量为j的情况，下装下最重的石头的重量
        int[][] dp = new int[len + 1][target + 1];

        for (int i = 1; i < len + 1; i++) {
            int stone = stones[i - 1];
            for (int j = target; j >= stone; j--) {

                dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - stone] + stone);
            }
        }

        return sum - 2 * dp[len][target];
    }


    public static void main(String[] args) {
        int[] stones = new int[]{1, 2};
        LastStoneWeightii lastStoneWeightii = new LastStoneWeightii();
        int i = lastStoneWeightii.lastStoneWeightII1(stones);
        System.out.println(i);
    }
}
